The detection and correction of errors that occur during the transmission of data is crucial to ensuring the reliability and integrity of data. A number of techniques of detecting the corruption of data during transmission are widely employed. At one end of the scale, a simple parity-checking method may be employed. Where more sophisticated detection and correction capabilities are required, checksum or Cyclic Redundancy Check methods are used.
Merely for example, a Cyclic Redundancy Check is a technique for preserving the integrity of a frame (or packet) that is being propagated from a data source to a data destination. Broadly, the Cyclic Redundancy Check (CRC) methodology requires that an n-bit sequence CRC, which may be a Frame Check Sequence (FCS), be generated for a frame, and appended to the frame prior to propagation from the data source. The CRC is propagated, together with the associated frame, from the data source to the data destination, and the CRC can then be utilized at the data destination to detect any corruption of the frame that may have occurred during transmission thereof.
An understanding of the generation of a CRC requires the definition of a number of structures, namely:
1. an "original frame", this being the frame to be transmitted, and being k. bits in length. The original frame may include data and header portions; PA0 2. the CRC which is n-bits in length; PA0 3. a "resulting frame", this frame being the combination of the original frame and the CRC, and having a total length of k+n bits; and PA0 4. a predetermined CRC polynomial having a length of n+1 bits.
The CRC is generated so that the resulting frame is exactly divisible by the predetermined CRC polynomial. Accordingly, the CRC creation process at the data source involves receiving the original frame and shifting it n bits to the left. The shifted original frame is then divided by the predetermined CRC polynomial, the remainder of this division process then being the CRC. The CRC is then appended to the original frame to generate the resulting frame. The CRC check process at the data destination involves receiving the resulting frame, and dividing the resulting frame by the predetermined CRC polynomial. The remainder of this division process is then examined and, if it is not zero, the resulting frame has probably experience corruption during transmission. The Cyclic Redundancy Check (CRC) technique is advantageous in that it provides good error detection capabilities, requires little overhead and is relatively easy to implement.
When propagating data over a network, such as a Local Area Network (LAN), Wide Area Network (WAN), intranet or the Internet, the data is encapsulated with header information according to the network protocols employed by the relevant network. For example, a packet or frame, comprising a data portion and appropriate headers, may include a header from a physical layer, a header from a network layer and a header from a transport layer. FIG. 1 shows an example of a frame 10, or packet, conforming to the ethernet specification. The frame 10 includes a preamble 12, a destination address 14, a source address 16, a length or EtherType value 18, a data portion 20 and a CRC 22. The destination address 14 occupies 6 bytes of the frame 10, and identifies a data destination at which the frame 10 is to be received. A destination address of all one's (111's) may be used to indicate a broadcast message to be received at all data destinations of the network. The source address 16 also occupies 6 bytes of the frame 10, and specifies the data source from which the frame 10 originated. The length or EtherType value 18 occupies 2 bytes, and may indicate the length of the frame 10, excluding the preamble 12, the CRC 22 and the length value 18 itself. A "raw" ethernet frame may not have a length shorter that 64 bytes or longer the 1518 bytes.
The value 18 may also indicate an Ethernet type to which the frame 10 belongs, in which case the frame 10 may include further header information not shown in FIG. 1. For example, an EtherType value 18 could identify the frame 10 as being an Ethernet II, Ethernet SNAP (SubNetwork Access Protocol) or Ethernet IEEE 802.2 frame. The destination address 14, source address 16 and the length or EtherType value 18 together comprise a data link header 24. The frame 10 may include further headers, such as a Logical Link Control (LLC) header (not shown) or a SNAP header (not shown) to conform the frame 10 to the IEEE 802.2 and SNAP formats respectively. The data portion 20 follows the header 24, and may occupy between 38 and 1492 bytes, and may comprise upper layer headers and user data.
The CRC 22 is 4 bytes in length. The CRC 22 is generated utilizing all preceding bytes within the frame 10. As such, it will be appreciated that should any modification be made to the frame 10, the CRC 22 generated using the unmodified frame will be invalid. Such modifications may comprise encapsulating the frame 10 by inserting further header information into the frame 10, or modifying data within the data portion 20. For example, referring to FIG. 2, the ethernet frame 10 of FIG. 1 may be encapsulated as a Virtual Local Area Network (VLAN) frame 30 by the insertion of a VLAN type code 32 and a VLAN number (or identifier) 34 into the ethernet frame 10 to generate the VLAN frame 30. Similarly, the VLAN frame 30 may be unencapsulated by the removal of the fields 32 and 34 to reveal the ethernet frame 10. Such modifications to the contents of a frame require that the CRC 22 must either be modified or recalculated to be applicable to the contents of the modified frame.
One way in which the CRC 22 could be modified when header information is added to the frame 10 (or removed from the frame 30) is by the addition of supplementary bytes to the CRC 22, which would then allow the CRC 22 to be validated for the modified frame. However, this has the disadvantage that the length of the modified frame is then increased. This increase in frame length is undesirable from both transmission and hardware viewpoints. Specifically, an increased frame length could impact negatively on buffer design within data source and destination devices.
A second option is to calculate a fresh CRC utilizing the all preceding bytes of a modified frame, and to then discard the original CRC generated using the unmodified frame. This option has the disadvantage that the original CRC for the unmodified frame is discarded upon modification of the original frame, and that any data corruption which may have occurred after the generation of the original CRC and prior to the modification of the frame (and the accompanying recalculation of the CRC) will become undetectable The possibility of data corruption, which occurred after the generation of the original CRC, going undetected is highly undesirable.